public class Test {
    class ListNode {
     int val;
     ListNode next;
     ListNode(int x) {
          val = x;
          next = null;
       }
    }
    //环形链表
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null&&fast.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow) {
                break;
            }
        }
        if(fast==null||fast.next==null) {
            return null;
        }
        while(head!=slow) {
            head = head.next;
            slow = slow.next;
        }
        return head;
    }

    //链表分割
    public class Partition {
        public ListNode partition(ListNode pHead, int x) {
            if(pHead==null) return null;
            ListNode as = null,ae = null;
            ListNode bs = null,be = null;
            ListNode cur = pHead;
            while(cur!=null) {
                if(cur.val<x) {
                    if(as==null){
                        as = ae = cur;
                    }else{
                        ae.next = cur;
                        ae = ae.next;
                    }
                }else {
                    if(bs==null) {
                        bs = be = cur;
                    }else {
                        be.next = cur;
                        be = be.next;
                    }
                }
                cur = cur.next;
            }
            if(as==null) {
                return bs;
            }
            if(bs == null) {
                return as;
            }
            ae.next = bs;
            be.next = null;
            return as;
        }
    }

    //求相交链表的交点
    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            int lenA = 0;
            int lenB = 0;
            ListNode curA = headA;
            ListNode curB = headB;
            while(curA!=null) {
                curA = curA.next;
                lenA++;
            }
            while(curB!=null) {
                curB=curB.next;
                lenB++;
            }
            ListNode longList = headA;
            ListNode shortList = headB;
            if(lenA<lenB) {
                longList = headB;
                shortList = headA;
            }
            int cnt = Math.abs(lenA-lenB);
            while(cnt>0) {
                longList = longList.next;
                cnt--;
            }
            while(longList!=shortList) {
                longList = longList.next;
                shortList = shortList.next;
            }
            return longList;
        }
    }
}
